Evolución gramatical

La evolución gramatical es una técnica relativamente nueva de computación evolutiva iniciada por Conor Ryan, JJ Collins y Michael O'Neill en 1998​ en el Grupo BD S en la Universidad de Limerick.

Se relaciona con la idea de Programación Genética en que el objetivo es encontrar un programa ejecutable o fragmento de programa, que logre un buen valor de comportamiento para la función objetivo dada. En la mayoría de los trabajos publicados sobre la Programación Genética, una expresión en forma de árbol es estructurada al estilo LISP se maneja directamente, mientras que la Evolución gramatical aplica operadores genéticos (operador genético) a una cadena de números enteros, posteriormente asignada a un programa mediante el uso de una gramática.

Uno de los beneficios de Evolución Gramatical (GE) es que este mapeo simplifica la aplicación de la búsqueda a diferentes lenguajes de programación y otras estructuras.

Problema abordado

En la programación genética al estilo convencional de Koza, el conjunto de funciones debe cumplir el requisito de cierre: todas las funciones deben ser capaces de aceptar como argumentos la salida de todas las demás funciones en el conjunto de funciones.

Por lo general, esto se implementa tratando con un único tipo de datos, como punto flotante de doble precisión. Mientras que los marcos de programación genética modernos apoyan la tipificación, tales sistemas de tipo tienen limitaciones que la evolución gramatical no sufre.

La solución de Evolución Gramatical

Evolución Gramatical ofrece una solución a este problema mediante la evolución de las soluciones de acuerdo a una gramática especificada por el usuario (por lo general una gramática en la forma de Backus-Naur). Por lo tanto, el espacio de búsqueda puede ser restringido, y el conocimiento del dominio del problema puede ser incorporado. La inspiración para este enfoque viene de un deseo de separar el "genotipo" del "fenotipo": visto desde el punto de vista de la Programación Genética, los objetos sobre los que opera el algoritmo de búsqueda y lo que la función de evaluación de la aptitud interpreta son una y la misma. En contraste, los "genotipos" de Evolución Gramatical son listas ordenadas de números enteros que se codifican para seleccionar reglas de la gramática libre de contexto proporcionada. El fenotipo, sin embargo, es el mismo que en el estilo Koza: una estructura similar a un árbol que se evalúa recursivamente. Este modelo está más en línea con la forma en que la genética funciona en la naturaleza, donde hay una separación entre el genotipo de un organismo y la expresión final del fenotipo en las proteínas, etc.

Observe que los objetos de la Evolución Gramatical actúan como buscador de la misma manera que son utilizado en los algoritmos genéticos. Esto significa, en principio, que cualquier paquete de algoritmo genético existente, como el popular GAlib, puede utilizarse para llevar a cabo la búsqueda, y un desarrollador que implemente un sistema de Evolución Gramatical sólo debe preocuparse por llevar a cabo el mapeo desde la lista de enteros hasta el árbol de programas. También es posible en principio realizar la búsqueda utilizando algún otro método, como la optimización del enjambre de partículas (véase la observación a continuación); La naturaleza modular de la Evolución Gramatical crea muchas oportunidades para los híbridos a medida que el problema de interés es resultó.

Brabazon y O'Neill han aplicado con éxito la Evolución Gramatical para predecir la quiebra corporativa, la previsión de índices bursátiles, las calificaciones crediticias de bonos y otras aplicaciones financieras. La Evolución Gramatical también se ha utilizado con el clásico modelo predador-presa para explorar el impacto de los parámetros tales como la eficacia de los depredadores, el número de nichos y mutaciones aleatorias sobre la estabilidad ecológica.​

Es posible estructurar una gramática evolutiva que para un conjunto de función / terminal dado es equivalente a la programación genética.

Críticas

A pesar de sus éxitos, la Evolución Gramatical ha sido objeto de algunas críticas. Un problema es que como resultado de su operación de mapeo, los operadores genéticos no alcanzan una alta localidad,​​ que es una propiedad altamente considerada de los operadores genéticos en algoritmos evolutivos.​

Variantes

Aunque la Evolución Gramatical es relativamente nueva, ya hay versiones mejoradas y variantes que han sido elaboradas. Los investigadores han experimentado con el uso de optimización de enjambre de partículas para llevar a cabo la búsqueda en lugar de algoritmos genéticos con resultados comparables a los de la Evolución Gramatical normal. Esto se conoce como un "enjambre gramatical"; Utilizando sólo el modelo PSO básico se ha encontrado que PSO es probablemente igualmente capaz de llevar a cabo el proceso de búsqueda en gramáticas evolutivas como son los algoritmos genéticos simples. (Aunque PSO es normalmente un paradigma de búsqueda de coma flotante, puede ser discretizado, por ejemplo, simplemente redondeando cada vector al número entero más cercano, usándolo con Evolución Gramatical ).

Otra posible variación que se ha experimentado en la literatura es intentar codificar información semántica en la gramática con el fin de sesgar más el proceso de búsqueda.

Véase también

• Programación genética

Notas

• Datos: Q5593687